class Solution
{
public:
    bool parseBoolExpr(string expression)
    {
        stack<char> s;
        for (auto c : expression)
        {
            if (c == ',')
            {
                continue;
            }
            else if (c == ')')
            {
                int trueCount = 0;
                int falseCount = 0;
                while (true)
                {
                    char opNum = s.top();
                    s.pop();
                    if (opNum == 't')
                    {
                        ++trueCount;
                    }
                    else if (opNum == 'f')
                    {
                        ++falseCount;
                    }
                    else if (opNum == '(')
                    {
                        break;
                    }
                }
                char operation = s.top();
                s.pop();
                if (operation == '!')
                {
                    if (falseCount)
                    {
                        s.push('t');
                    }
                    else
                    {
                        s.push('f');
                    }
                }
                else if (operation == '|')
                {
                    if (trueCount)
                    {
                        s.push('t');
                    }
                    else
                    {
                        s.push('f');
                    }
                }
                else if (operation == '&')
                {
                    if (falseCount)
                    {
                        s.push('f');
                    }
                    else
                    {
                        s.push('t');
                    }
                }
            }
            else
            {
                s.push(c);
            }
        }
        return s.top() == 't';
    }
};